<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML 2.0//EN">
<html><head>
<meta http-equiv="content-type" content="text/html; charset=ISO-8859-1">
<!--Converted with LaTeX2HTML 96.1 (Feb 5, 1996) by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds -->


<title>Power Crisis</title>
<meta name="description" content="Power Crisis">
<meta name="keywords" content="htmlatex">
<meta name="resource-type" content="document">
<meta name="distribution" content="global">
<link rel="STYLESHEET" href="acm-00151_archivos/htmlatex.css">
</head><body bgcolor="#ffffff" lang="EN">
 <h1><br clear="all"><center><table bgcolor="#0060f0"><tbody><tr><td><b><font color="#c0ffff" size="5">&nbsp;<a name="SECTION0001000000000000000000">Power Crisis</a></font>&nbsp;</b></td></tr></tbody></table></center></h1>
<p>
During the power crisis in New Zealand this winter (caused by a
shortage of rain and hence low levels in the hydro dams), a
contingency scheme was developed to turn off the power to areas of the
country in a systematic, totally fair, manner. The country was divided
up into <i>N</i> regions (Auckland was region number 1, and Wellington number
13). A number, <i>m</i>, would be picked `at random', and the power would
first be turned off in region 1 (clearly the fairest starting point)
and then in every m'th region after that, wrapping around to 1 after
<i>N</i>, and ignoring regions already turned off. For example, if <i>N</i> = 17 and
<i>m</i> = 5, power would be turned off to the regions in the
order:1,6,11,16,5,12,2,9,17,10,4,15,14,3,8,13,7.
</p><p>
</p><p>
The problem is that it is clearly fairest to turn off Wellington last
(after all, that is where the Electricity headquarters are), so for a
given <i>N</i>, the `random' number <i>m</i> needs to be carefully chosen so that
region 13 is the last region selected.
</p><p>
</p><p>
Write a program that will read in the number of regions and then
determine the smallest number <i>m</i> that will ensure that Wellington
(region 13) can function while the rest of the country is blacked out.
</p><p>
</p><h2><font color="#0070e8"><a name="SECTION0001001000000000000000">Input and Output</a></font></h2>
<p>
Input will consist of a
series of lines, each line containing the number of regions (<i>N</i>) with
 <img alt="tex2html_wrap_inline42" src="acm-00151_archivos/151img1.gif" align="middle" height="26" width="104"> . The file will be terminated by a line consisting of
a single 0.
</p><p>
</p><p>
Output will consist of a series of lines, one for each line of the
input. Each line will consist of the number <i>m</i> according to the above
scheme.
</p><p>
</p><h2><font color="#0070e8"><a name="SECTION0001002000000000000000">Sample input</a></font></h2>
<p>
</p><pre>17
0</pre>
<p>
</p><h2><font color="#0070e8"><a name="SECTION0001003000000000000000">Sample output</a></font></h2>
<p>
</p><pre>7</pre>
<p>
</p></body></html>